Distributed Computing
A distributed system must handle partial failures: one computer or network path can fail while the rest of the system keeps running.
What happens when only part of the system fails?
The real problems roses only, when partial failures happens, because they introduce nondeterministic operations to the environment which might cause inconsistencies and unpredictable results.
Useful vocabulary for these notes: Network Time Protocol (NTP) adjusts computer clocks but cannot make them identical; a monotonic clock measures elapsed time without jumping backward. Last-write-wins (LWW) chooses the update with the latest timestamp. A fencing token is an increasing number that a storage system checks to reject writes from an old leader. Safety means nothing bad happens, while liveness means useful progress eventually happens.
There are two main types of computing environment.
- #supercomputers
- #cloudscomputing
Super computers always prefer to escalate partial failure to total failure, thus keeping consistency. Partial failure its a real deal on cloud computing by which we depend upon side effects on network and real life.
The usual way to handle the possibility of an receiver not receiving or responding from a request is a timeout. But for how long?
Premature timeouts: if you declare a node dead prematurely, you can overload the entire cluster. If there only too much overload causing a delay in the response time, killing nodes may even increase it further.
Late timeouts: can cause an horrifying experience for the end-user and a performance hit.
For enterprise application on cloud enviroments, you need to decide the timeout experimentally. Monitoring it and taking into account the context of the application logic. Even so, dynamically changing it with metrics. Suggestions : Phi Accrucal failure detector.
#clocks
we can separate the usage of clocks and time on software on two categories:
- points in time
- duration/measure
The time comes always from the hardware, which may not be synchronized perfectly. Time-of-day clocks are not suitable for measuring elapsed time because machines can disagree even after NTP adjustment. Use a monotonic clock for durations.
if your software requires high precision for time of day and synchronized clocks, you need to ensure the offset of all nodes, if one drifts way too much, declare it dead.
One clear example is syncrhonization of data on replicas, with #lastwritewins #lww. which depends on the timestamp from the change..
Databases such as Spanner, utilize the timestamp to generate a transaction id for Snapshop isolation. Since generating transaciton id on distributed databases can be conflicting.
Garbage collection (GC), real-time operating systems (RTOS), and process pauses can all affect observed timing.
Another critical and dangerous usage of clocks, is to lock processes depending on timestamps(ex: timeouts)
Partitions with single leaders often use a lease. Each elected leader receives time-limited authority and must renew it before it expires.
For example, renewal can be delayed by a garbage-collection pause, container suspension, heavy I/O, disk swapping, closing a laptop lid, or stopping a Unix process.
Preventing GC : the runtime can actually notify that the node will go through GC and routing any traffic to other instance. Or simply kill the node and restart before long-lived object GC.
One way to prevent leases and corruption of date, when writing with single leader. is to add fencing tokens to lease.
Whenever we claim a lease, we also issue a fencing token—an increasing number—and reject writes from a node whose token is no longer current.
For example, ZooKeeper can provide a transaction identifier (zxid) or node version as a fencing token.
Whenever we are modeling a system, we should categorize them an assume what can and cannot happen so we can write our algorithms.
Timing models can be synchronous (known time bounds), partially synchronous (bounds hold only sometimes), or asynchronous (no timing bound can be assumed).
And regarding fault-tolerance, we can categorize it as:
- crash-stop faults, where a machine stops and does not return;
- crash-recovery faults, where it stops and later returns using persisted data;
- Byzantine faults, where a participant can send incorrect or deceptive messages.
Algorithms must have an correctness based on some properties, that can be #liveness properties or #safety. such as uniqueness, #monotonicsequence, #availability
To map real world to system model we need to make assumptions, and even handle edge cases that were never meant to happen, requiring human work.